1. Field of the Invention
The present invention relates generally to a low-density parity-check (LDPC) encoder, an LDPC decoder, and LDPC encoding and decoding methods, and more particularly to an LDPC encoder, an LDPC decoder, and LDPC encoding and decoding methods in which the size of a memory of the encoder and decoder can be reduced by forming a small LDPC code from a large LDPC code (also called parity check matrix).
2. Description of Related Art
The low-density parity-check (LDPC) code invented in 1962 by Robert Gallager is a linear block code defined by a very sparse parity check matrix, which is populated primarily with zeros and sparsely with ones. When it was first introduced, the LDPC code was too complicated to implement, and so it was forgotten for a long time until not too long ago. The LDPC code was brought to light again in 1995, and an irregular LDPC code (which is a generalization of the LDPC code suggested by Robert Gallager) was introduced in 1998. When the LDPC code was first introduced by Gallager, a probabilistic decoding algorithm was also suggested, and the LDPC code which is decoded using this algorithm exhibited excellent performance characteristics. The LDPC code also showed improved performance when extended to non-binary code as well as binary code to define code words. Like the turbo code, the LDPC code yields a bit error rate (BER) approaching a Shannon channel capacity limit, which is the theoretical maximum amount of digital data that can be transmitted in a given bandwidth in presence of a certain noise interference. The irregular LDPC code which is known to have the best performance only needs an additional 0.13 dB from the Shannon channel capacity to achieve a BER of 10−6 when a code length is a million bits in an additive white Gaussian noise (AWGN) channel environment, and is thus suitable for applications which require high-quality transmission with a very low BER.
Unlike algebraic decoding algorithms usually used for decoding a block code, the decoding algorithm of the LDPC code is a probabilistic decoding algorithm to which a belief-propagation algorithm, which employs a graph theory and a guessing theory, is applied “as is”. An LDPC decoder computes a probability of a bit corresponding to each bit of a code word received through a channel being “1” or “0”. The probability information computed by the LDPC decoder is referred to as a message, and the quality of the message can be checked through each parity defined in a parity check matrix. If a certain parity of the parity check matrix is satisfied, i.e., the result of a parity check is positive, the computed message is specially referred to as a parity check message and contains the most probable value of each code word bit. The parity check message for each parity is used to determine the value of a corresponding bit, and information on a computed bit is referred to as a bit message. Through a procedure of repeating such message transmission, the information for bits of each code word comes to satisfy all parities of the parity-check matrix. Finally, when all parities of the parity-check matrix are satisfied, the decoding of the code word is finished. In an environment where a signal to noise (S/N) ratio is low, systematic codes are used, and thus certain portions of the code word are extracted to reproduce information bits.
If a channel is a frequency selective fading channel, adaptive modulation and coding is used for low-error communication. The LDPC code is a type of block channel code and thus has the disadvantage of being difficult to adaptively modulate compared to a trellis code such as a convolution code or a turbo code to which a desired form of modulation and coding can easily be applied through puncturing. In order for the LDPC code to support various code rates for adaptive transmission, it has to have various code matrices, which carries the disadvantage of the encoder and the decoder needing a large memory.